/**
 * @file 022.链表中环的入口节点.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-20
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct ListNode {
    ListNode(int val = 0, ListNode *next = nullptr)
        : val(val), next(next) {}
    int val;
    ListNode *next;
};

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        if (!head) {
            return nullptr;
        }
        ListNode *slow = head, *fast = head;
        bool hasCycle = false;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle) {
            return nullptr;
        }
        fast = head;
        while (fast) {
            if (slow == fast) {
                return slow;
            }
            fast = fast->next;
            slow = slow->next;
        }
        return nullptr;
    }
};